class Task41Heap:
    def __init__(self):
        self.min_heap = []
        self.max_heap = []
        self.n = 0

    def insert(self, num):
        self.n += 1
        if self.n % 2 == 0:
            if len(self.min_heap) > 0 and num > self.min_heap[0]:
                # insert into min heap
                self.insert_into_min_heap(num)
                min_value = self.pop_min()
                self.insert_into_max_heap(min_value)
            else:
                self.insert_into_max_heap(num)
        else:
            if len(self.max_heap) > 0 and num < self.max_heap[0]:
                # insert into max heap
                self.insert_into_max_heap(num)
                max_value = self.pop_max()
                self.insert_into_min_heap(max_value)
            else:
                self.insert_into_min_heap(num)

    def get_median(self):
        if self.n % 2 == 0:
            return (self.max_heap[0] + self.min_heap[0]) / 2
        else:
            return self.min_heap[0]

    def insert_into_min_heap(self, num):
        self.min_heap.append(num)
        n = (len(self.min_heap) // 2) - 1
        for i in reversed(range(n + 1)):
            self.sift_down_min(self.min_heap, i)

    def insert_into_max_heap(self, num):
        self.max_heap.append(num)
        n = (len(self.max_heap) // 2) - 1
        for i in reversed(range(n + 1)):
            self.sift_down_max(self.max_heap, i)

    def pop_min(self):
        self.min_heap[0], self.min_heap[-1] = self.min_heap[-1], self.min_heap[0]
        min_value = self.min_heap.pop()
        if len(self.min_heap) > 0:
            self.sift_down_min(self.min_heap, 0)
        return min_value

    def pop_max(self):
        self.max_heap[0], self.max_heap[-1] = self.max_heap[-1], self.max_heap[0]
        max_value = self.max_heap.pop()
        if len(self.max_heap) > 0:
            self.sift_down_max(self.max_heap, 0)
        return max_value

    def sift_down_min(self, array, index):
        left_index = index * 2 + 1
        right_index = index * 2 + 2
        min_index = index
        if left_index < len(array) and array[left_index] < array[min_index]:
            min_index = left_index
        if right_index < len(array) and array[right_index] < array[min_index]:
            min_index = right_index
        if min_index != index:
            array[index], array[min_index] = array[min_index], array[index]
            self.sift_down_min(array, min_index)

    def sift_down_max(self, array, index):
        left_index = index * 2 + 1
        right_index = index * 2 + 2
        max_index = index
        if left_index < len(array) and array[left_index] > array[max_index]:
            max_index = left_index
        if right_index < len(array) and array[right_index] > array[max_index]:
            max_index = right_index
        if max_index != index:
            array[index], array[max_index] = array[max_index], array[index]
            self.sift_down_max(array, max_index)
